#include <iostream>
#include <cstdlib>
#include <vector>
#include <stack>
#include <queue>

template <class Comparable>
class BinarySearchTree {
public:
    BinarySearchTree(void) {
        root = NULL;
        makeEmpty();
    }
    BinarySearchTree(const BinarySearchTree &rhs) {
        this->operator=(rhs);
    }
    ~BinarySearchTree(void) {
        makeEmpty();
    }

    const Comparable& findMin(void) const {        
        return *findMax(root);
    }
    const Comparable& findMax(void) const {
        return *findMin(root);
    }

    bool contains(const Comparable& val) const {
        return contains(val, root);
    }

    bool isEmpty(void) const {
        return (root == NULL);
    }

    void makeEmpty(void) {
        makeEmpty(root);
    }

    void insert(const Comparable& val) {
        insert(val, root);
    }

    void remove(const Comparable& val) {
        remove(val, root);
    }

    const BinarySearchTree& operator=(const BinarySearchTree& rhs) {
        if (this != &rhs) {
            makeEmpty();
            root = clone(rhs.root);        
        }
        return *this;
    }

    //分层遍历，需要求树的深度
    void printByLevelOrder(void) const {
        const int dep = depth(root);
        for (int i = 0; i <= dep; ++i) {
            printAtLevel(root, i);
            std::cout << std::endl;
        }
    }

    //层序遍历，不求树的深度
    void printByLevelOrder2(void) const {
        for (int i = 0; ; ++i) {
            if (!printAtLevel(root, i)) {
                break;
            }
            std::cout << std::endl;
        }
    }

    //层序遍历，利用数组加速访问
    void printByLevelOrder3(void) const {
        if (root == NULL)
            return ;
        std::vector<BinaryNode*> vect;
        vect.push_back(root);
        size_t cur = 0, last = 1;
        while (cur < vect.size()) {
            last = vect.size();
            for (; cur < last; ++cur) {//遍历该层
                if (vect[cur]->left) {//左子树不为空，则添加至下一层
                    vect.push_back(vect[cur]->left);
                }
                if (vect[cur]->right) {//右子树不为空，则添加至下一层
                    vect.push_back(vect[cur]->right);
                }
                visit(vect[cur]);
            }
            std::cout << std::endl;
        }
    }

    //层序遍历，利用队列实现
    void printByLevelOrder4(void) const {
        if (root == NULL)
            return ;
        std::queue<BinaryNode*> q;
        q.push(root);
        while (!q.empty()) {
            BinaryNode* t = q.front();
            visit(t);
            q.pop();
            if (t->left != NULL) {//左子树不为空，则添加至下一层
                q.push(t->left);
            }
            if (t->right != NULL) {//右子树不为空，则添加至下一层
                q.push(t->right);
            }
        }
        std::cout << std::endl;
    }
    
    //层序遍历，从下至上访问
    void printByLevelOrder5(void) const {
        const int dep = depth(root);
        for (int i = dep; i >= 0; --i) {
            printAtLevel(root, i);
            std::cout << std::endl;
        }
    }

    //前序遍历，递归调用
    void printByPreOrder(void) const {
        printByPreOrder(root);
        std::cout << std::endl;
    }

    //前序遍历，非递归，利用栈实现
    void printByPreOrder2(void) const {
        BinaryNode* t = root;
        std::stack<BinaryNode*> s;
        while (t != NULL || !s.empty()) {
            if (t != NULL) {
                visit(t);
                s.push(t);
                t = t->left;
            } else {                
                t = s.top();
                s.pop();
                t = t->right;
            }
        }
        std::cout << std::endl;
    }

    //中序遍历，递归调用
    void printByInOrder(void) const {       
        printByInOrder(root);
        std::cout << std::endl;
    }

    //中序遍历，非递归调用，利用栈实现
    void printByInOrder2(void) const {        
        BinaryNode* t = root;
        std::stack<BinaryNode*> s;
        while (t != NULL || !s.empty()) {
            if (t != NULL) {
                s.push(t);
                t = t->left;
            } else {                
                t = s.top();
                visit(t);
                s.pop();
                t = t->right;
            }
        }
        std::cout << std::endl;
    }

    //后序遍历，递归实现
    void printByPostOrder(void) const {      
        printByPostOrder(root);
        std::cout << std::endl;
    }

    //后序遍历，非递归调用，利用栈实现
    void printByPostOrder2(void) const {
        BinaryNode* t = root;
        BinaryNode* top = NULL;
        BinaryNode* pre = NULL;
        std::stack<BinaryNode*> s;
        while (t != NULL || !s.empty()) {
            if (t != NULL) {
                s.push(t);
                t = t->left;
            } else {
                top = s.top();
                if (top->right != NULL && top->right != pre) {
                    t = top->right;
                } else {
                    visit(top);
                    pre = top;
                    s.pop();
                }
            }
        }
        std::cout << std::endl;
    }

private:
    struct BinaryNode {
        BinaryNode(const Comparable& val, BinaryNode* l, BinaryNode* r)
            : element(val), left(l), right(r) {}
        Comparable  element;
        BinaryNode* left;
        BinaryNode* right;
    };
    BinaryNode *root;

    void visit(BinaryNode* node) const {
        if (node != NULL) {
            std::cout << node->element << " ";
        }
    }

    int depth(BinaryNode* t) const {
        if (t == NULL) {
            return -1;
        } else {
            return 1 + std::max(depth(t->left), depth(t->right));
        }
    }

    bool contains(const Comparable& val, BinaryNode* t) const {
        if (t == NULL) {
            return false;
        } else {
            if (t->element == val) {
                return true;
            } else if (val < t->element) {
                return contains(val, t->left);
            } else {
                return contains(val, t->right);
            }
        }
    }

    BinaryNode* findMin(const Comparable &val, BinaryNode* t) const {
        if (t != NULL) {
            while (t->left != NULL) {
                t = t->left;
            }
        }
        return t;
    }

    BinaryNode* findMax(const Comparable &val, BinaryNode* t) const {
        if (t != NULL) {
            while (t->right != NULL) {
                t = t->right;
            }
        }
        return t;
    }

    void makeEmpty(BinaryNode*& t) {
        if (t != NULL) {
            makeEmpty(t->left);
            makeEmpty(t->right);
            delete t;
        }
        t = NULL;
    }

    void insert(const Comparable &val, BinaryNode*& t) {
        if (t == NULL) {
            t = new BinaryNode(val, NULL, NULL);
        } else if (t->element == val) {
            ;
        } else if (val < t->element) {
            insert(val, t->left);
        } else {
            insert(val, t->right);
        }
    }

    void remove(const Comparable &val, BinaryNode*& t) {
        if (t == NULL) {
            return ;
        } else if (val < t->element) {
            remove(val, t->left);
        } else if (val > t->element) {
            remove(val, t->right);
        } else if (t->left != NULL && t->right != NULL) {
            //有两个孩子
            t->element = findMin(t->right, t->right)->element;
            remove(t->element, t->right);
        } else {
            //只有一个孩子
            BinaryNode* old = t;
            t = (t->left != NULL) ? t->left : t->right;
            delete old;
        }
    }

    BinaryNode* clone(BinaryNode*& t) {
        if (t != NULL) {
            return new BinaryNode(t, clone(t->left), clone(t->right));
        } else {
            return NULL;
        }
    }

    int printAtLevel(BinaryNode* t, int level) const {
        if (t == NULL || level < 0) {
            return 0;
        }
        if (level == 0) {
            visit(t);
            return 1;
        } else {
            return printAtLevel(t->left, level-1) + printAtLevel(t->right, level-1);
        }
    }

    void printByPreOrder(BinaryNode* t) const {
        if (t != NULL) {
            visit(t);
            printByPreOrder(t->left);
            printByPreOrder(t->right);
        }
    }

    void printByInOrder(BinaryNode* t) const {
        if (t != NULL) {
            printByInOrder(t->left);
            visit(t);
            printByInOrder(t->right);
        }
    }

    void printByPostOrder(BinaryNode* t) const {
        if (t != NULL) {
            printByPostOrder(t->left);
            printByPostOrder(t->right);
            visit(t);
        }
    }
};

int main(int argc, const char *argv[])
{
//    int A[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
    int A[] = {23, 112, 54, 4, 6, 7, 24, 56, 2, 33, 11};
    BinarySearchTree<int> tree;
    for (int i = 0; i < (int)(sizeof(A)/sizeof(int)); ++i) {
        tree.insert(A[i]);
    }
    std::cout << "print by level : 1" << std::endl;
    tree.printByLevelOrder();
    std::cout << "print by level : 2" << std::endl;
    tree.printByLevelOrder2();
    std::cout << "print by level : 3" << std::endl;
    tree.printByLevelOrder3();
    std::cout << "print by level : 4" << std::endl;
    tree.printByLevelOrder4();
    std::cout << "print by level : from bottom to top" << std::endl;
    tree.printByLevelOrder5();

    std::cout << "print by pre order : 1" << std::endl;
    tree.printByPreOrder();
    std::cout << "print by pre order : 2" << std::endl;
    tree.printByPreOrder2();
   
    std::cout << "print by in order : 1" << std::endl;
    tree.printByInOrder();
    std::cout << "print by in order : 2" << std::endl;
    tree.printByInOrder2();

    std::cout << "print by post order : 1" << std::endl;
    tree.printByPostOrder();
    std::cout << "print by post order : 2" << std::endl;
    tree.printByPostOrder2();

    return 0;
}
